import java.util.Arrays;

public class 检查边长度限制的路径是否存在 {

    /**
     * https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/
     * 核心: 排序完查询数组, 最小生成树到要求权值, 看一下两个点有没有在一个并查集中
     */

    public static int MAXN = 100001;
    public static int[] farther = new int[MAXN];
    public static int[][] questions = new int[MAXN][4];

    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        //创建questions是为了标号, 因为排序权值之后要保持顺序
        for(int i = 0;i < queries.length;i++){
            questions[i][0] = queries[i][0];
            questions[i][1] = queries[i][1];
            questions[i][2] = queries[i][2];
            questions[i][3] = i;

        }
        //排序一下图和查询的
        Arrays.sort(edgeList,(x,y) -> x[2] - y[2]);
        Arrays.sort(questions,0,queries.length,(x,y) -> x[2] - y[2]);
        build(n);
        boolean[] ans = new boolean[queries.length];

        for(int cnt = 0,i = 0;cnt < queries.length;cnt++){
            for(;i < edgeList.length && edgeList[i][2] < questions[cnt][2];i++){
                union(edgeList[i][0],edgeList[i][1]);
            }
            ans[questions[cnt][3]] = isSameSet(questions[cnt][0],questions[cnt][1]);
        }
        return ans;
    }

    private void build(int n) {
        for (int i = 0; i < n; i++) {
            farther[i] = i;
        }
    }

    private static int find(int i) {
        if(farther[i] != i){
            farther[i] = find(farther[i]);
        }
        return farther[i];
    }

    private static void union(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            farther[fx] = fy;
        }
    }

    private static boolean isSameSet(int x,int y){
        return find(x) == find(y);
    }
}
